This is an algorithm for filling in any digitally formed outline of an area, including those with concave outlines, and specifically comprises a method of segmenting the entire area into trapezoids which are more easily filled.
In the past, it was typical for each printing equipment manufacturer to design his text generating machines in the form of terminals and typewriters, image forming equipment in the form of scanners for pictures and computers for graphics, and printers, to interface directly with one another. However, there was no standardization between manufacturers. Equipment from one manufacturer could not be used with equipment from another, and large industry inefficiencies resulted. Stated differently, there was no industry wide standard interface that could be used between pieces of publishing systems.
To remedy this problem, the Interpress Printing Language and the standard Interpress Interface were created and adopted by some manufacturers. Now, for example, using the Interpress language and protocols, grahics generated on one manufacturers computer can be printed on another's printer.
One standard feature in a publishing system is the requirement of filling in, at the time of publishing, an area that had been originally defined as an outline at the graphics generating station. More specifically, the outline received by the printing system may be defined in the form of vectors, while the printer itself needs its information in the form of rasters. The problem is made more difficult when the outline defined by vectors has concave portions, where the vectors cross each other as in a five-cornered star, or where the outline comprises separate but overlapping shapes.
By way of definition, an outline is said to be composed of trajectories, each trajectory being made up of a series of connected vectors. For example, a five pointed star comprises one trajectory comprising five vectors. Another case is the filling in of areas that are formed by one set of vectors within, or partially overlaying, another set of vectors. For example, a trajectory comprising four vectors defining a square may be overlapped or enclosed within a second trajectory comprising a three vector triangle. These outlines may or may not be filled in correctly depending on the algorithm used.
A known method for determining the areas of an outline that should be filled in is the calculation of a winding number. This method is described in the Interpress Xerox System Integration Standard, pages 56 and 57. The winding number is the number of times the area in question is surrounded by an outline, and is the count of the surrounding clockwise closed trajectories minus the count of the surrounding counterclockwise closed trajectories. The remaining problem is how to divide up the outline into manageable areas that can be conveniently filled in by the hardware or software.
An algorithm can be constructed that will calculate, for each point, whether that point is within the vector-defined area by testing whether the current point is within a connected set of vectors that exist above, below and to both sides of the point, but this kind of program is time consuming.
In the case of crossed vectors and concave outlines, there may be several vectors in each direction which have to be handled by the computation, and, depending on the algorithm, these computations may not be accomplished correctly. To make sure that the outline is processed properly, the graphics generator may be set up to generate a complex form in simple parts and have them filled separately to generate the whole complex area.
What is required, in a system that is to be used in the Interpress environment, is an algorithm for finding the optimum set of areas to allow the efficient fill-in by a raster scanner printer of any outline, regardless of complexity, originally defined as trajectories by the graphics generating equipment.